As described in U.S. patent application Ser. No. 10/839995, which is incorporated by reference herein, a low-density parity-check (LDPC) code is a linear block code specified by a parity-check matrix H. In general, an LDPC code is defined over a Galois Field GF(q), q≧2. If q=2, the code is a binary code. All linear block codes can be described as the product of a k-bit information block S1×k with a code generator matrix Gk×n, to produce an n-bit codeword x1×n, where the code rate is r=k/n. The codeword x is transmitted through a noisy channel, and the received signal vector y is passed to the decoder to estimate the information block S1×k.
Given an n-dimensional space, the rows of G span the k-dimensional codeword subspace C, and the rows of the parity-check matrix Hm×n span the m-dimensional dual space C , where m=n-k. Since x=sG and GHT=0, it follows that xHT=0 for all codewords in subspace C, where “T” (or “T”) denotes matrix transpose. In the discussion of LDPC codes, this is generally written asHxT=0T,  (1)where 0 is a row vector of all zeros, and the codeword x=[s p]=[s0, s1, . . . , sk-1, p0, p1, . . . , pm-1], where p0, . . . , pm-l are the parity-check bits; and s0, . . . , sk-1 are the systematic bits, equal to the information bits within the information block.
During operation, a receiver obtains a contaminated version y of the transmitted codeword x. To decode y and determine the original information block s, an iterative decoding algorithm, such as belief propagation, is applied based on a bipartite graph. Soft information, usually in the format of log-likelihood ratio (LLR) of the codeword bits, is passed between the bank of variable nodes and the bank of check nodes. The iteration is stopped either when all check equations are satisfied or a maximum allowed iteration limit is reached.
The physical layer of a communication system must often be designed to provide higher layers (e.g., medium access control) the capability of transferring a wide range of packet sizes, and the physical layer forward error correction scheme must be designed accordingly. For instance, the rate-½ low-density parity-check (LDPC) code in IEEE 802.16e was defined over information block sizes k ranging from 36 to 144 bytes, inclusive, in 6-byte increments.
The structured LDPC codes in IEEE 802.16e and 802.11n are defined in terms of a “model” parity-check matrix and an “expansion factor” z, where the entries of the model matrix represent either the z×z null matrix or one of the z cyclic shift permutation matrices of size z×z. Thus, each row of the model matrix defines a vector of parity checks. With this structure an LDPC decoder can efficiently “evaluate” a vector of parity-check equations in parallel. Cyclic shifting of the soft information between the parity-check equations is an important aspect of the decoder. A high-throughput decoder must perform the shift in as few clock cycles as possible.
For a given code rate, the IEEE 802.16e and 802.11n LDPC codes accommodate multiple code sizes n by fixing the model matrix size and changing the expansion factor z to match the desired code sizes. This is referred to here as the “single-model” method. For example, in IEEE 802.16e nineteen 24-column model matrices are defined for z ranging from 24 to 96, inclusive, in increments of 4. Changing z changes the size of the vector of parity checks, and a vectorized decoder must hence support cyclic shifting over these vector sizes. Thus, in the single-model method a vectorized LDPC encoder and/or decoder will need to incorporate hardware for cyclic shifting over multiple vector sizes (i.e., one for each expansion factor). This greatly increases the complexity of the encoder and decoder. Therefore, a need exists for a method and apparatus for encoding and decoding data that reduces the amount of hardware necessary for cyclic shifting, yet allows for multiple code sizes to be utilized.